package _06_动态规划;

public class _53_最大子序和 {

    // 分治解法
    public int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length);
    }

    public int maxSubArray(int[] nums, int begin, int end) {
        if (end - begin < 2) return nums[begin];
        int mid = begin + end >> 1;
        int leftMax = nums[mid - 1];
        int leftTotal = leftMax;
        for (int i = mid - 2; i >= begin; i--) {
            leftTotal += nums[i];
            leftMax = Math.max(leftMax, leftTotal);
        }

        int rightMax = nums[mid];
        int rightTotal = rightMax;
        for (int i = mid + 1; i < end; i++) {
            rightTotal += nums[i];
            rightMax = Math.max(rightMax, rightTotal);
        }

        return Math.max(leftMax + rightMax,
                Math.max(maxSubArray(nums, begin, mid), maxSubArray(nums, mid, end)));
    }

    // 动态规划
    public int maxSubArray1(int[] nums) {
        int max, curMax;
        max = curMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curMax = Math.max(nums[i], nums[i] + curMax);
            max = Math.max(max, curMax);
        }
        return max;
    }

}
